package Josephus

/*
时间复杂度：O(N)
空间复杂度：O(1)

约瑟夫环问题: f(n, m) = f(n-1, m)%n (后面取模的n与前面f(n,m)中的n对应)
			f(n-1, m) = (f(n-2, m)+m)%(n-1)
*/

func lastRemaining(n int, m int) int {
	//当只有一个人时，返回第一个人的编号，即0
	flag := 0
	for i := 2; i <= n; i++ {
		//k == m - 1 ==> m = k+1
		//y = (x+k+1)%n => y = (x+m)%n
		flag = (flag + m) % i
	}
	return flag
}
